home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 98 / Skunkware 98.iso / src / mail / db.1.85.tar.gz / db.1.85.tar / db.1.85 / btree / bt_debug.c < prev    next >
C/C++ Source or Header  |  1994-08-18  |  9KB  |  330 lines
  1. /*-
  2.  * Copyright (c) 1990, 1993, 1994
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)bt_debug.c    8.5 (Berkeley) 8/17/94";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #include <sys/param.h>
  42.  
  43. #include <stdio.h>
  44. #include <stdlib.h>
  45. #include <string.h>
  46.  
  47. #include <db.h>
  48. #include "btree.h"
  49.  
  50. #ifdef DEBUG
  51. /*
  52.  * BT_DUMP -- Dump the tree
  53.  *
  54.  * Parameters:
  55.  *    dbp:    pointer to the DB
  56.  */
  57. void
  58. __bt_dump(dbp)
  59.     DB *dbp;
  60. {
  61.     BTREE *t;
  62.     PAGE *h;
  63.     pgno_t i;
  64.     char *sep;
  65.  
  66.     t = dbp->internal;
  67.     (void)fprintf(stderr, "%s: pgsz %d",
  68.         F_ISSET(t, B_INMEM) ? "memory" : "disk", t->bt_psize);
  69.     if (F_ISSET(t, R_RECNO))
  70.         (void)fprintf(stderr, " keys %lu", t->bt_nrecs);
  71. #undef X
  72. #define    X(flag, name) \
  73.     if (F_ISSET(t, flag)) { \
  74.         (void)fprintf(stderr, "%s%s", sep, name); \
  75.         sep = ", "; \
  76.     }
  77.     if (t->flags != 0) {
  78.         sep = " flags (";
  79.         X(R_FIXLEN,    "FIXLEN");
  80.         X(B_INMEM,    "INMEM");
  81.         X(B_NODUPS,    "NODUPS");
  82.         X(B_RDONLY,    "RDONLY");
  83.         X(R_RECNO,    "RECNO");
  84.         X(B_METADIRTY,"METADIRTY");
  85.         (void)fprintf(stderr, ")\n");
  86.     }
  87. #undef X
  88.  
  89.     for (i = P_ROOT; (h = mpool_get(t->bt_mp, i, 0)) != NULL; ++i) {
  90.         __bt_dpage(h);
  91.         (void)mpool_put(t->bt_mp, h, 0);
  92.     }
  93. }
  94.  
  95. /*
  96.  * BT_DMPAGE -- Dump the meta page
  97.  *
  98.  * Parameters:
  99.  *    h:    pointer to the PAGE
  100.  */
  101. void
  102. __bt_dmpage(h)
  103.     PAGE *h;
  104. {
  105.     BTMETA *m;
  106.     char *sep;
  107.  
  108.     m = (BTMETA *)h;
  109.     (void)fprintf(stderr, "magic %lx\n", m->magic);
  110.     (void)fprintf(stderr, "version %lu\n", m->version);
  111.     (void)fprintf(stderr, "psize %lu\n", m->psize);
  112.     (void)fprintf(stderr, "free %lu\n", m->free);
  113.     (void)fprintf(stderr, "nrecs %lu\n", m->nrecs);
  114.     (void)fprintf(stderr, "flags %lu", m->flags);
  115. #undef X
  116. #define    X(flag, name) \
  117.     if (m->flags & flag) { \
  118.         (void)fprintf(stderr, "%s%s", sep, name); \
  119.         sep = ", "; \
  120.     }
  121.     if (m->flags) {
  122.         sep = " (";
  123.         X(B_NODUPS,    "NODUPS");
  124.         X(R_RECNO,    "RECNO");
  125.         (void)fprintf(stderr, ")");
  126.     }
  127. }
  128.  
  129. /*
  130.  * BT_DNPAGE -- Dump the page
  131.  *
  132.  * Parameters:
  133.  *    n:    page number to dump.
  134.  */
  135. void
  136. __bt_dnpage(dbp, pgno)
  137.     DB *dbp;
  138.     pgno_t pgno;
  139. {
  140.     BTREE *t;
  141.     PAGE *h;
  142.  
  143.     t = dbp->internal;
  144.     if ((h = mpool_get(t->bt_mp, pgno, 0)) != NULL) {
  145.         __bt_dpage(h);
  146.         (void)mpool_put(t->bt_mp, h, 0);
  147.     }
  148. }
  149.  
  150. /*
  151.  * BT_DPAGE -- Dump the page
  152.  *
  153.  * Parameters:
  154.  *    h:    pointer to the PAGE
  155.  */
  156. void
  157. __bt_dpage(h)
  158.     PAGE *h;
  159. {
  160.     BINTERNAL *bi;
  161.     BLEAF *bl;
  162.     RINTERNAL *ri;
  163.     RLEAF *rl;
  164.     indx_t cur, top;
  165.     char *sep;
  166.  
  167.     (void)fprintf(stderr, "    page %d: (", h->pgno);
  168. #undef X
  169. #define    X(flag, name) \
  170.     if (h->flags & flag) { \
  171.         (void)fprintf(stderr, "%s%s", sep, name); \
  172.         sep = ", "; \
  173.     }
  174.     sep = "";
  175.     X(P_BINTERNAL,    "BINTERNAL")        /* types */
  176.     X(P_BLEAF,    "BLEAF")
  177.     X(P_RINTERNAL,    "RINTERNAL")        /* types */
  178.     X(P_RLEAF,    "RLEAF")
  179.     X(P_OVERFLOW,    "OVERFLOW")
  180.     X(P_PRESERVE,    "PRESERVE");
  181.     (void)fprintf(stderr, ")\n");
  182. #undef X
  183.  
  184.     (void)fprintf(stderr, "\tprev %2d next %2d", h->prevpg, h->nextpg);
  185.     if (h->flags & P_OVERFLOW)
  186.         return;
  187.  
  188.     top = NEXTINDEX(h);
  189.     (void)fprintf(stderr, " lower %3d upper %3d nextind %d\n",
  190.         h->lower, h->upper, top);
  191.     for (cur = 0; cur < top; cur++) {
  192.         (void)fprintf(stderr, "\t[%03d] %4d ", cur, h->linp[cur]);
  193.         switch (h->flags & P_TYPE) {
  194.         case P_BINTERNAL:
  195.             bi = GETBINTERNAL(h, cur);
  196.             (void)fprintf(stderr,
  197.                 "size %03d pgno %03d", bi->ksize, bi->pgno);
  198.             if (bi->flags & P_BIGKEY)
  199.                 (void)fprintf(stderr, " (indirect)");
  200.             else if (bi->ksize)
  201.                 (void)fprintf(stderr,
  202.                     " {%.*s}", (int)bi->ksize, bi->bytes);
  203.             break;
  204.         case P_RINTERNAL:
  205.             ri = GETRINTERNAL(h, cur);
  206.             (void)fprintf(stderr, "entries %03d pgno %03d",
  207.                 ri->nrecs, ri->pgno);
  208.             break;
  209.         case P_BLEAF:
  210.             bl = GETBLEAF(h, cur);
  211.             if (bl->flags & P_BIGKEY)
  212.                 (void)fprintf(stderr,
  213.                     "big key page %lu size %u/",
  214.                     *(pgno_t *)bl->bytes,
  215.                     *(u_int32_t *)(bl->bytes + sizeof(pgno_t)));
  216.             else if (bl->ksize)
  217.                 (void)fprintf(stderr, "%s/", bl->bytes);
  218.             if (bl->flags & P_BIGDATA)
  219.                 (void)fprintf(stderr,
  220.                     "big data page %lu size %u",
  221.                     *(pgno_t *)(bl->bytes + bl->ksize),
  222.                     *(u_int32_t *)(bl->bytes + bl->ksize +
  223.                     sizeof(pgno_t)));
  224.             else if (bl->dsize)
  225.                 (void)fprintf(stderr, "%.*s",
  226.                     (int)bl->dsize, bl->bytes + bl->ksize);
  227.             break;
  228.         case P_RLEAF:
  229.             rl = GETRLEAF(h, cur);
  230.             if (rl->flags & P_BIGDATA)
  231.                 (void)fprintf(stderr,
  232.                     "big data page %lu size %u",
  233.                     *(pgno_t *)rl->bytes,
  234.                     *(u_int32_t *)(rl->bytes + sizeof(pgno_t)));
  235.             else if (rl->dsize)
  236.                 (void)fprintf(stderr,
  237.                     "%.*s", (int)rl->dsize, rl->bytes);
  238.             break;
  239.         }
  240.         (void)fprintf(stderr, "\n");
  241.     }
  242. }
  243. #endif
  244.  
  245. #ifdef STATISTICS
  246. /*
  247.  * BT_STAT -- Gather/print the tree statistics
  248.  *
  249.  * Parameters:
  250.  *    dbp:    pointer to the DB
  251.  */
  252. void
  253. __bt_stat(dbp)
  254.     DB *dbp;
  255. {
  256.     extern u_long bt_cache_hit, bt_cache_miss, bt_pfxsaved, bt_rootsplit;
  257.     extern u_long bt_sortsplit, bt_split;
  258.     BTREE *t;
  259.     PAGE *h;
  260.     pgno_t i, pcont, pinternal, pleaf;
  261.     u_long ifree, lfree, nkeys;
  262.     int levels;
  263.  
  264.     t = dbp->internal;
  265.     pcont = pinternal = pleaf = 0;
  266.     nkeys = ifree = lfree = 0;
  267.     for (i = P_ROOT; (h = mpool_get(t->bt_mp, i, 0)) != NULL; ++i) {
  268.         switch (h->flags & P_TYPE) {
  269.         case P_BINTERNAL:
  270.         case P_RINTERNAL:
  271.             ++pinternal;
  272.             ifree += h->upper - h->lower;
  273.             break;
  274.         case P_BLEAF:
  275.         case P_RLEAF:
  276.             ++pleaf;
  277.             lfree += h->upper - h->lower;
  278.             nkeys += NEXTINDEX(h);
  279.             break;
  280.         case P_OVERFLOW:
  281.             ++pcont;
  282.             break;
  283.         }
  284.         (void)mpool_put(t->bt_mp, h, 0);
  285.     }
  286.  
  287.     /* Count the levels of the tree. */
  288.     for (i = P_ROOT, levels = 0 ;; ++levels) {
  289.         h = mpool_get(t->bt_mp, i, 0);
  290.         if (h->flags & (P_BLEAF|P_RLEAF)) {
  291.             if (levels == 0)
  292.                 levels = 1;
  293.             (void)mpool_put(t->bt_mp, h, 0);
  294.             break;
  295.         }
  296.         i = F_ISSET(t, R_RECNO) ?
  297.             GETRINTERNAL(h, 0)->pgno :
  298.             GETBINTERNAL(h, 0)->pgno;
  299.         (void)mpool_put(t->bt_mp, h, 0);
  300.     }
  301.  
  302.     (void)fprintf(stderr, "%d level%s with %ld keys",
  303.         levels, levels == 1 ? "" : "s", nkeys);
  304.     if (F_ISSET(t, R_RECNO))
  305.         (void)fprintf(stderr, " (%ld header count)", t->bt_nrecs);
  306.     (void)fprintf(stderr,
  307.         "\n%lu pages (leaf %ld, internal %ld, overflow %ld)\n",
  308.         pinternal + pleaf + pcont, pleaf, pinternal, pcont);
  309.     (void)fprintf(stderr, "%ld cache hits, %ld cache misses\n",
  310.         bt_cache_hit, bt_cache_miss);
  311.     (void)fprintf(stderr, "%ld splits (%ld root splits, %ld sort splits)\n",
  312.         bt_split, bt_rootsplit, bt_sortsplit);
  313.     pleaf *= t->bt_psize - BTDATAOFF;
  314.     if (pleaf)
  315.         (void)fprintf(stderr,
  316.             "%.0f%% leaf fill (%ld bytes used, %ld bytes free)\n",
  317.             ((double)(pleaf - lfree) / pleaf) * 100,
  318.             pleaf - lfree, lfree);
  319.     pinternal *= t->bt_psize - BTDATAOFF;
  320.     if (pinternal)
  321.         (void)fprintf(stderr,
  322.             "%.0f%% internal fill (%ld bytes used, %ld bytes free\n",
  323.             ((double)(pinternal - ifree) / pinternal) * 100,
  324.             pinternal - ifree, ifree);
  325.     if (bt_pfxsaved)
  326.         (void)fprintf(stderr, "prefix checking removed %lu bytes.\n",
  327.             bt_pfxsaved);
  328. }
  329. #endif
  330.